package com.leetCode.ListNodeDemo;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public class MergeKListsDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(4);
        queue.offer(2);
        queue.offer(3);
        queue.offer(1);
        while (!queue.isEmpty()){
            System.out.println("队列数据:" + queue.poll());
        }
    }

    /**
     * 给你一个链表数组，每个链表都已经按升序排列。
     *
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     *
     * 示例 1：
     *
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     * 示例 2：
     *
     * 输入：lists = []
     * 输出：[]
     * 示例 3：
     *
     * 输入：lists = [[]]
     * 输出：[]
     * 提示：
     *
     * k == lists.length
     * 0 <= k <= 10^4
     * 0 <= lists[i].length <= 500
     * -10^4 <= lists[i][j] <= 10^4
     * lists[i] 按 升序 排列
     * lists[i].length 的总和不超过 10^4
     * Related Topics
     * 链表
     * 分治
     * 堆（优先队列）
     * 归并排序
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0){
            return null;
        }
        if (lists.length == 1){
            return lists[0];
        }
        List<Integer> valueList = new ArrayList<>();
        for (int i = 0;i < lists.length;i++){
            ListNode listNode = lists[i];
            while (listNode != null){
                valueList.add(listNode.val);
                listNode = listNode.next;
            }
        }
        List<Integer> sortValueList = valueList.stream().sorted().collect(Collectors.toList());
        ListNode rootNode = new ListNode();
        ListNode tempNode = null;
        for (int i = 0;i < sortValueList.size();i++){
            ListNode newNode = new ListNode(sortValueList.get(i));
            if (tempNode == null){
                rootNode.next = newNode;
            } else {
                tempNode.next = newNode;
            }
            tempNode = newNode;
        }
        return rootNode.next;
    }

    /**
     * 分治思想
     */
    public static ListNode mergeKLists1(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public static ListNode merge(ListNode[] lists, int l, int r){
        if (l == r){
            return lists[l];
        }
        if (l < r){
            return null;
        }
        int mid = lists.length / 2;
        return mergeTwoLists(merge(lists,l,mid),merge(lists,mid + 1,r));
    }

    public static ListNode mergeTwoLists(ListNode a,ListNode b){
        if (a == null || b == null){
            return a == null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a,bPtr = b;
        while (aPtr != null && bPtr != null){
            if (aPtr.val < bPtr.val){
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

/**
 * 优先队列
 * 维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，
 * 每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。
 */
class Solution {
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }

    public ListNode mergeKLists1(ListNode[] lists){
        for (ListNode node : lists){
            if (node != null){
                queue.offer(new Status(node.val,node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()){
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null){
                queue.offer(new Status(f.ptr.next.val,f.ptr.next));
            }
        }
        return head.next;
    }
}


